Cantorova diagonálna metóda

Cantorova diagonálna metóda je matematický dôkaz, pomocou ktorého Georg Cantor dokázal, že množina všetkých reálnych čísel je nespočítateľná.

Diagonálna metóda nebola prvým dôkazom, ktorý Cantor použil k dokázaniu tohto faktu, bola publikovaná tri roky po prvom dôkaze. Na druhej strane je oproti pôvodnému dôkazu oveľa známejšia, navyše bol princíp metódy použitý na dokázanie mnohých ďalších viet (napríklad problém zastavenia).

Dôkaz

Cantorov dôkaz ukazuje, že interval [0,1] nie je spočítateľný.

Dôkaz sporom:

1. Predpokladajme, že interval [0,1] je spočítatelne nekonečný.
2. Môžeme teda „zapísat“ všetky čísla do postupnosti (r₁, r₂, r₃, …)
3. Každé z týchto čísel možno zapísať v desatinnom rozvoji.
4. Zoraďme tieto čísla (nemusia byť zoradené v prirodzenom usporiadaní). Predpokladajme napríklad, že začiatok nášho zoznamu vyzerá takto:

   r₁ = 0 , 5 1 0 5 1 1 0 …

   r₂ = 0 , 4 1 3 2 0 4 3 …

   r₃ = 0 , 8 2 4 5 0 2 6 …

   r₄ = 0 , 2 3 3 0 1 2 6 …

   r₅ = 0 , 4 1 0 7 2 4 6 …

   r₆ = 0 , 9 9 3 7 8 3 8 …

   r₇ = 0 , 0 1 0 5 1 3 5 …

   …

5. Zostrojme reálne číslo x ležiace v intervale [0,1] tak, že pre k-tú číslicu v jeho desatinnom rozvoji vezmeme do úvahy k-tú číslicu v desatinnom rozvoji r_k. Číslice, ktoré berieme do úvahy, sú v následujúcej postupnosti zvýraznené (aby bolo vidno, prečo sa dôkaz nazýva diagonálna metóda).

   r₁ = 0 , 5 1 0 5 1 1 0 …

   r₂ = 0 , 4 1 3 2 0 4 3 …

   r₃ = 0 , 8 2 4 5 0 2 6 …

   r₄ = 0 , 2 3 3 0 1 2 6 …

   r₅ = 0 , 4 1 0 7 2 4 6 …

   r₆ = 0 , 9 9 3 7 8 3 8 …

   r₇ = 0 , 0 1 0 5 1 3 5 …

   …

6. Z týchto číslic definujeme číslice čísla x nasledovne:
   • pokiaľ je na k-tom mieste v r_k číslica α ∈ {0,1,2,3,4,5,6,7,8,9} potom na k-tom mieste v x bude číslica β ∈ ({0,1,2,3,4,5,6,7,8,9} - {α})
7. zjednodušene napr.:
   • pokiaľ je na k-tom mieste v r_k číslica 5 potom na k-tom mieste v x bude 4,
   • pokiaľ nie je na k-tom mieste v r_k číslica 5 potom na k-tom mieste v x bude 5.
8. Číslo x je zjavne reálne (keďže všetky desatinné rozvoje reprezentujú reálne číslo) z intervalu [0,1]. Napríklad pre hore uvedenú postupnosť by x vyzeralo takto:

   x = 0 , 4 5 5 5 5 5 4 …

9. Musí teda existovať r_n = x pre nejaké n, keďže sme predpokladali, že v postupnosti (r₁, r₂, r₃, …) sú všetky reálne čísla z intervalu [0, 1].
10. Ale vďaka spôsobu zostrojenia čísla x sa x líši od každého r_n na n-tom desatinnom mieste, teda x neleží v postupnosti (r₁, r₂, r₃, …)
11. Táto sekvencia teda nie je sekvenciou všetkých reálných čísel z intervalu [0,1], dochádzame k sporu.
12. Z toho vyplýva, že predpoklad, že interval [0,1] je spočítateľný, je nepravdivý.

Zdroj

Matematický portál

Tento článok je čiastočný alebo úplný preklad článku Cantorova diagonální metoda na českej Wikipédii.